package com.gozap.sort.spec;

/**
 * 由于词算法涉及到复制数组导致无法使用统一接口
 * @author yaoming
 *
 */
public class MergeSort {

	/**
	 * 合并排序
	 * 
	 * @param arr
	 * @param begin数组下标
	 * @param end数组下标
	 */
	public void merge(int[] arr, int begin, int end) {
		if (end > begin) {
			int mid = (begin + end) / 2;
			int lenBefore = mid - begin + 1;
			int lenAfter = end - mid;

			int[] before = new int[lenBefore];
			int[] after = new int[lenAfter];

			for (int i = begin; i <= mid; i++) {
				before[i - begin] = arr[i];
			}

			for (int i = mid + 1; i <= end; i++) {
				after[i - mid - 1] = arr[i];
			}

			merge(before, 0, lenBefore - 1);
			merge(after, 0, lenAfter - 1);

			int i = begin;
			int bIndex = 0;
			int aIndex = 0;

			while (bIndex < lenBefore && aIndex < lenAfter) {
				if (before[bIndex] < after[aIndex]) {
					arr[i] = before[bIndex];
					bIndex++;
				} else {
					arr[i] = after[aIndex];
					aIndex++;
				}
				i++;
			}
			if (bIndex < lenBefore) {
				for (int j = bIndex; j < lenBefore; j++) {
					arr[i] = before[j];
					i++;
				}
			} else if (aIndex < lenAfter) {
				for (int j = aIndex; j < lenAfter; j++) {
					arr[i] = after[j];
					i++;
				}
			}

		}
	}

	public static void print() {
		int len = arr.length;
		for (int i = 0; i < len; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	static int arr[] = { 4, 5, 3, 9, 8, 7, 98, 72, 10, 12, 8, 6, 20, 15, 60, 45,
			2, 43, 11, 50 };

	public static void main(String[] args) {

		MergeSort sort = new MergeSort();
		sort.merge(arr, 0, arr.length - 1);
		print();
		System.out.print("\n======");
	}
}
